package com.hanxiaozhang.dynamicprogramming;

/**
 * 〈一句话功能简述〉<br>
 * 〈给定数组arr，arr中所有的值都为正数且不重复，
 *  每个值代表一种面值的货币，每种面值的货币可以使用任意张，
 *  再给定一个整数aim，代表要找的钱数，求组成 aim 的方法数。〉
 *
 * @author hanxinghua
 * @create 2021/10/21
 * @since 1.0.0
 */
public class CoinsWay {

    public static void main(String[] args) {
        int[] arr = {5, 2, 3, 1};
        int sum = 350;
        System.out.println(ways(arr, sum));
        System.out.println(dpWays(arr, sum));
        System.out.println(dpWays1(arr, sum));
        System.out.println(dpWays2(arr, sum));
    }

    /**
     * arr中都是正数且无重复值，返回组成aim的方法数
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int ways(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        return process(arr, 0, aim);
    }


    /**
     * 如果自由使用arr[index...]的面值，组成rest这么多钱，返回方法数 （1 , 6）
     *
     * @param arr
     * @param index
     * @param rest
     * @return
     */
    public static int process(int[] arr, int index, int rest) {
        // base case  没有货币的时候
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        // 有货币的时候 arr[index] 当钱面值
        int ways = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            ways += process(arr, index + 1, rest - zhang * arr[index]);
        }
        return ways;
    }

    /**
     * 动态规划，添加傻缓存
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int dpWays(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        // 缓存表
        int[][] dp = new int[arr.length + 1][aim + 1];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = -1;
            }
        }
        return process1(arr, 0, aim, dp);
    }

    /**
     * 递归
     *
     * @param arr
     * @param index
     * @param rest
     * @param dp
     * @return
     */
    public static int process1(int[] arr, int index, int rest, int[][] dp) {
        // dp[index][rest] != -1 证明有值，直接返回
        if (dp[index][rest] != -1) {
            return dp[index][rest];
        }
        // base case  没有货币的时候
        if (index == arr.length) {
            return dp[index][rest] = rest == 0 ? 1 : 0;
        }
        // 有货币的时候 arr[index] 当钱面值
        int ways = 0;
        for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
            ways += process1(arr, index + 1, rest - zhang * arr[index], dp);
        }
        return dp[index][rest] = ways;
    }



    /**
     * 动态规划，精简方法 等效 动态规划，添加傻缓存
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int dpWays1(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        //   通过base case
        //   if (index == arr.length) {return rest == 0 ? 1 : 0; }
        //   得知 dp[N][0] = 1
        dp[N][0] = 1;
        // 整体从下行往上行推出值， 每一行从左往右退出
        for (int index = N - 1; index >= 0; index--) {
            for (int rest = 0; rest <= aim; rest++) {
                int ways = 0;
                for (int zhang = 0; zhang * arr[index] <= rest; zhang++) {
                    ways += dp[index + 1][rest - (zhang * arr[index])];
                }
                dp[index][rest] = ways;
            }
        }
        return dp[0][aim];
    }


    /**
     * 动态规划，精简方法，替代枚举
     *
     * @param arr
     * @param aim
     * @return
     */
    public static int dpWays2(int[] arr, int aim) {
        if (arr == null || arr.length == 0 || aim < 0) {
            return 0;
        }
        int N = arr.length;
        int[][] dp = new int[N + 1][aim + 1];
        //   通过base case
        //   if (index == arr.length) {return rest == 0 ? 1 : 0; }
        //   得知 dp[N][0] = 1
        dp[N][0] = 1;
        for (int i = N - 1; i >= 0; i--) {
            for (int rest = 0; rest <= aim; rest++) {
                // 下一行赋值给上一行
                dp[i][rest] = dp[i + 1][rest];
                // 如果剩余可用钱数 -当前货币面值大于0
                if (rest - arr[i] >= 0) {
                    // dp[i][rest]加上当前这行[rest - 当前货币面值]的缓存值
                    dp[i][rest] += dp[i][rest - arr[i]];
                }
            }
        }
        return dp[0][aim];
    }

}
